/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

/**
 * <p>标题：解码方法</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/decode-ways/
 * </pre>
 * <p>创建日期：2019年11月25日上午10:12:11</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code91DecodeWays</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code91DecodeWays
{
	public static void main(String[] args)
	{
		/**
		 * 一条包含字母 A-Z 的消息通过以下方式进行了编码：

		'A' -> 1
		'B' -> 2
		...
		'Z' -> 26
		给定一个只包含数字的非空字符串，请计算解码方法的总数。

		示例 1:

		输入: "12"
		输出: 2
		解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
		示例 2:

		输入: "226"
		输出: 3
		解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
		 */
		int numDecodings = numDecodings("1231313114123213131");
		System.out.println(numDecodings);
	}

	/**
	 * 本题采用动态规划思路:
	 * 		字符串记为：S m=s.length()
	 * 				S(i)表示坐标i对应的字符
	 * 				S(i,j)表示坐标i到坐标j的字符，包括j	注：在程序中是包左不包右，需+1，这里只是作思路解题用
	 * 		记dp[i]为指定节点长度的解码方法数
	 * 		则有：
	 * 			dp[i] = dp[i-1]+dp[i-2]
	 * 		考虑各种情况：
	 * 			dp[i]:{
	 * 					无法翻译，直接返回0：{
	 * 							和0组成的数字大于26 
	 * 							连续两个字符都为0
	 * 							字符串以0开头
	 * 						},
	 * 					dp[0]:{
	 * 							1, S(0)!=0
	 * 							0, S(0)==0
	 * 						},
	 * 					dp[1]:{
	 * 							0,	(S(1)==0 and S(0)==0) or(S(1)==0 and S(0,1)>26)
	 * 							1,	(S(0,1)>26 and S(1)!=0) or (S(1)==0 and S(0,1)<=26)
	 * 							2,	S(1)!=0 and S(0,1)<=26	
	 * 						},
	 * 					dp[i]:{
	 * 							0,	(S(i)==0 and S(i-1)==0)	or (S(i)==0 and S(i-1,i)>26)
	 * 							dp[i-2],	S(i)==0 and S(i-1,i)<=26	即只能是最后两位构成翻译码，无法拆开，因此直接取dp[i-2]的组合即可
	 * 							dp[i-1],	S(i-1)==0 and S(i)!=0	即倒数第二位是0，则不用考虑最后一位是什么，他不影响数量的计算，直接考虑该位之前的就行
	 * 							dp[i-1],	S(i)!=0 and S(i-1)!=0 and S(i-1,i)>26	也是不用考虑最后一位，因为他无法和前一位组成翻译码，则直接考虑该位之前的就行
	 * 							dp[i - 1] + dp[i - 2],		S(i)!=0 and S(i-1)!=0 and S(i-1,i)<=26
	 * 						}
	 * 				}
	 * 
	 * 时间复杂度：O(n)
	 * 空间复杂度：O(n)
	 * 		
	 * @param s
	 * @return
	 */
	public static int numDecodings(String s)
	{
		//1.以0开头则返回0
		if (s.startsWith("0"))
		{
			return 0;
		}
		//2.初始化dp数组
		int[] dp = new int[s.length()];
		//3.初始化dp[0]
		dp[0] = 1;
		//4.初始化的dp[1]
		if (s.length() > 1)
		{
			if (s.charAt(1) == '0')
			{
				if (Integer.parseInt(s.substring(0, 2)) <= 26)
				{
					dp[1] = 1;
				} else
				{
					dp[1] = 0;
				}
			} else if (Integer.parseInt(s.substring(0, 2)) <= 26)
			{
				dp[1] = 2;
			} else
			{
				dp[1] = 1;
			}
		} else
		{
			return 1;
		}
		//循环初始化第i位的dp[i]值
		for (int i = 2; i < s.length(); i++)
		{
			char c1 = s.charAt(i);
			char c2 = s.charAt(i - 1);
			int parse = Integer.parseInt(s.substring(i - 1, i + 1));
			if (c1 == '0')
			{
				if (c2 == '0')
				{
					return 0;
				} else
				{
					//101
					if (parse <= 26)
					{
						dp[i] = dp[i - 2];
					} else
					{
						return 0;
					}
				}
			} else
			{
				if (c2 == '0')
				{
					dp[i] = dp[i - 1];
				} else
				{
					if (parse <= 26)
					{
						dp[i] = dp[i - 1] + dp[i - 2];
					} else
					{
						dp[i] = dp[i - 1];
					}
				}
			}
		}
		for (int i = 0; i < dp.length; i++)
		{
			System.out.print(dp[i] + "\t");
		}
		System.out.println();
		return dp[s.length() - 1];
	}
}
